1. Field of the Invention
Methods and apparatuses consistent with the present invention relate to encoding and decoding an image, and more particularly, to a method and apparatus for encoding and decoding an image based on a result of prediction by more precisely predicting a current block by performing consecutive motion estimation a plurality of times.
2. Description of the Related Art
In image compression methods such as Moving Picture Experts Group-1 (MPEG-1), MPEG-2 or MPEG-4 H.264/MPEG-4 AVC (Advanced Video Coding), one picture is divided into predetermined image processing units so as to encode an image. Then, each image processing unit is encoded using inter prediction or intra prediction. Here, image processing units may be macro blocks. An optimum encoding mode is selected by considering the size of data and the degree of distortion of an original macro block, and an image processing unit is encoded according to the selected encoding mode.
In a method of encoding an image using inter prediction, temporal redundancy between pictures is removed and an image is compressed. A motion estimation encoding method is a representative method of encoding an image by using inter prediction.
In the motion estimation encoding method, motion of a current block is estimated using at least one reference picture, motion compensation is performed according to the result of motion estimation, and an image is encoded. In the motion estimation encoding method, the most similar reference block to the current block is searched within a predetermined range of reference pictures by using a predetermined evaluation function. A block having the smallest sum of absolute differences (SAD) with the current block is searched as a reference block. The reference block is an inter prediction block of the current block, and only a residual block obtained by subtracting the reference block from the current block is encoded and transmitted, thereby increasing the compression rate of data. Here, the current block may be formed to have various sizes such as 16×16, 8×16, 8×8, and 4×4 etc, which will now be described in detail with reference to FIG. 1.
FIG. 1 illustrates a conventional inter prediction method.
Referring to FIG. 1, when an image is encoded or decoded, inter prediction is preformed using at least one reference picture.
When a current block 112 of current picture 110 is inter predicted, an apparatus for encoding an image searches a prediction block 122 having the smallest SAD with the current block by searching a reference picture 120.
If the prediction block 122 is found, the prediction block 122 is subtracted from the current block 112 to generate a residual block. Then, the generated residual block is encoded to generate a bitstream. In this case, a motion vector 130, which is a relative difference between the position of the current block and the position of the prediction block 122 inside a picture, is encoded and inserted into the bitstream. Since only the residual block is transmitted, as the prediction block 122 is more similar to the current block 112, the compression rate of image encoding is improved.
However, the prediction block 122 having the smallest SAD with the current block 112 may exist in a previously encoded region of the current picture 110 (instead of in the reference picture 120). In particular, this occurs when a current picture includes an image in which a uniform pattern is repeatedly formed, as in an image depicting a texture. In this case, prediction encoding may be performed using a block included in the previously encoded region of the current picture 110.
An algorithm for removing such redundancy inside a picture has been suggested. However, prediction of a motion vector may be incorrect, and therefore the compression rate of image encoding is not greatly improved. Thus, a method and apparatus for encoding an image based on a more precise prediction block generated as a result of more effectively referring to a plurality of pictures including a current picture, are needed.